package LeetCode.month02.day51;
import LeetCode.month02.day50.ListNode;
public class No86 {
    public ListNode partition(ListNode head, int x) {
        ListNode newhead1 = new ListNode(0);
        ListNode newhead2 = new ListNode(0);
        ListNode curr = head;
        ListNode end1 = newhead1;
        ListNode end2 = newhead2;
        while(curr!=null){
            if(curr.val<x){
                end1.next = curr;
                end1 = end1.next;
            }else{
                end2.next = curr;
                end2 = end2.next;
            }
            curr = curr.next;
            end1.next=null;
            end2.next=null;
        }
        end1.next = newhead2.next;
        return newhead1.next;
    }
}
